/*
视频教程的典型算法:

	1 求解最大公约数  CommonGCD
	2 欧几里得算法    EuclidGCD
	3 扩展欧几里得算法（递归）
*/
package week02

// 功能: 常规求最大公约数, 蛮力法
//
//	@description: 选取两个里较小的数，对其依次减1验证
func CommonGCD(a, b int) int {
	if max := agreement1(&a, &b); max != 1 {
		return max // 约定 a>b
	}

	for i := b; i >= 1; i-- {
		if a%i == 0 && b%i == 0 {
			return i
		}
	}
	return 1
}

// 欧几里得算法（辗转相除法）
//
//	@param a, b [int] 非负非全0的两个整数
func EuclidGCD(a, b int) int {
	if max := agreement1(&a, &b); max != 1 {
		return max // 约定 a>b
	}

	for {
		if (a % b) == 0 {
			break
		}
		a, b = b, a%b
	}
	return b // 不能用a, a可能是b的倍数
}

// @description: 辗转相除法求最大公约数的递归写法
func ReursionGCD(a, b int) int {

	if (a % b) > 0 {
		return ReursionGCD(b, a%b)
	}
	return b
}

/*
扩展欧几里得算法
  @description: 已知 gcd(a,b)=d, 找出一组<x,y>, 满足 ax+by=d

  相当于确认A桶要倒掉几次，B桶需要倒入几次能达到要求。
*/
func ExternEuclid(a, b int) (x, y, d int) {
	if b == 0 {
		return 1, 0, a
	}
	x, y, d = ExternEuclid(b, a%b)
	q := a / b
	return y, (x - q*y), d
}

/*
功能: 约定

	1 输入的两个数第1个大, 第2个小(x>y)
	2 任何非0数和0的最大公约数是它本身

	@return [int]  返回1 表示符合约定
*/
func agreement1(x, y *int) int {
	if *x < *y {
		*x, *y = *y, *x // 平行赋值, 省去了交换的临时变量
	}
	if *y == 0 {
		return *x // 规则2
	}
	if *y < 0 {
		return 0
	}
	return 1
}
